//#include <iostream>
//#include <string>
//#include <algorithm>
//using namespace std;
//
//
//int q;
//
//string func(string& str)
//{
//    if (stoi(str) % 2 == 0) return str;
//    int n = str.size(), i = n - 2;
//    while (i >= 0)
//    {
//        if ((str[i] - '0') % 2 == 0)
//        {
//            swap(str[i], str[n - 1]);
//            break;
//        }
//        i--;
//    }
//    return (i >= 0) ? str : "-1";
//}
//
//int main()
//{
//    cin >> q;
//    while (q--)
//    {
//        string str; cin >> str;
//        cout << stoi(func(str).c_str()) << endl;
//    }
//    return 0;
//}




//#include <iostream>
//using namespace std;
//const int N = 15;
//int ret;
//int n;
//bool vis[N];
//int arr[N];
//void dfs(int pos)
//{
//	if (pos == n + 1)
//	{
//		ret++;
//		return;
//	}
//
//	for (int i = 1; i <= n; i++)
//	{
//		if (vis[i]) continue; 
//		if (vis[arr[i]]) return; 
//		vis[i] = true; 
//		dfs(pos + 1);
//		vis[i] = false; 
//	}
//}
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++) cin >> arr[i];
//
//	dfs(1);
//
//	cout << ret << endl;
//
//	return 0;
//}




class Solution
{
 public:
 int ret = -1010;
 int maxPathSum(TreeNode* root)
 {
	 dfs(root);
	 return ret;
 }
 int dfs(TreeNode* root)
 {
	 if (root == nullptr) return 0;
	 int l = max(0, dfs(root->left));
	 int r = max(0, dfs(root->right)); 
	 ret = max(ret, root->val + l + r);
	 return root->val + max(l, r);
 }
};